package com.practice.zuocy.base.class07;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 【题目】：求二叉树最宽的层有多少个节点
 */
public class Code06_TreeMaxWidth {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	/**
	 * 改写层序遍历的方法，求解树的最大宽度（需要发现一个层的开始和结束）。
	 * 使用HashMap记录一个层的开始和结束！！
	 *
	 * @param head 头节点
	 * @return 最大宽度
	 */
	public static int maxWidthUseMap(Node head) {
		if (head == null) {
			return 0;
		}
		Queue<Node> queue = new LinkedList<>();
		queue.add(head);
		// key 在 哪一层，value
		// key:节点，value:节点在哪一层。
		// 一个节点进队列就马上进Map
		HashMap<Node, Integer> levelMap = new HashMap<>();
		// 头节点在第1层
		levelMap.put(head, 1);
		// 当前你正在统计哪一层的宽度
		int curLevel = 1;
		// 当前层curLevel层，宽度目前是多少。进队列时不统计，出队列时再统计
		int curLevelNodes = 0;
		// 所有层的宽度的最大值
		int max = 0;
		while (!queue.isEmpty()) {
			// 弹出一个节点
			Node cur = queue.poll();
			// 该节点在哪一层
			int curNodeLevel = levelMap.get(cur);
			// 弹出节点的左孩子不为空，最还在进队列，并在Map中记录左孩子的层数
			if (cur.left != null) {
				levelMap.put(cur.left, curNodeLevel + 1);
				queue.add(cur.left);
			}
			// 弹出节点的右孩子不为空，最还在进队列，并在Map中记录右孩子的层数
			if (cur.right != null) {
				levelMap.put(cur.right, curNodeLevel + 1);
				queue.add(cur.right);
			}
			if (curNodeLevel == curLevel) {
				// 弹出节点所在层数和当前正在统计的层数相同，说明当前层没有过期，更新当前层的宽度（+1）
				curLevelNodes++;
			} else {
				// 弹出节点所在层数和当前正在统计的层数不相同（说明已经弹出了下一层的一个节点了！），说明当前层过期了，更新所有层的宽度的最大值
				max = Math.max(max, curLevelNodes);
				// 当前层++
				curLevel++;
				// 当前层的节点数变为1
				curLevelNodes = 1;
			}
		}
		// 最后一层是没有下一层触发结算“所有层的宽度的最大值”的，要在最后再更新一次“所有层的宽度的最大值”
		max = Math.max(max, curLevelNodes);
		return max;
	}

	/**
	 * 改写层序遍历的方法，求解树的最大宽度（需要发现一个层的开始和结束）。
	 * 不使用HashMap记录一个层的开始和结束！！
	 *
	 * @param head 头节点
	 * @return 最大宽度
	 */
	public static int maxWidthNoMap(Node head) {
		if (head == null) {
			return 0;
		}
		Queue<Node> queue = new LinkedList<>();
		// 头节点进队列
		queue.add(head);
		// 当前层，最右节点（最后一个节点）是谁。（第一次最右的节点就是头节点）
		Node curEnd = head;
		// 下一层（如果有下一层时），最右节点（最后一个节点）是谁
		Node nextEnd = null;
		// 所有层的宽度的最大值
		int max = 0;
		// 当前层的节点数（从队列中弹出的时候统计）
		int curLevelNodes = 0;
		while (!queue.isEmpty()) {
			// 弹出一个节点
			Node cur = queue.poll();
			if (cur.left != null) {
				// 弹出的节点有左孩子，左孩子加入队列
				queue.add(cur.left);
				// 下一层，最右节点更新为弹出节点的左孩子
				nextEnd = cur.left;
			}
			if (cur.right != null) {
				// 弹出的节点有右孩子，右孩子加入队列
				queue.add(cur.right);
				// 下一层，最右节点更新为弹出节点的右孩子
				nextEnd = cur.right;
			}
			// 当前层的节点数++
			curLevelNodes++;
			if (cur == curEnd) {
				// 如果弹出节点为当前层的最右节点，说明当前层要马上过期了（下一层一个节点还没有弹出），更新所有层的宽度的最大值
				max = Math.max(max, curLevelNodes);
				// 当前层的节点数边为0
				curLevelNodes = 0;
				// 马上要到下一层了，让当前层最右节点变为下一层最右节点
				curEnd = nextEnd;
			}
		}
		return max;
	}

	// for test
	public static Node generateRandomBST(int maxLevel, int maxValue) {
		return generate(1, maxLevel, maxValue);
	}

	// for test
	public static Node generate(int level, int maxLevel, int maxValue) {
		if (level > maxLevel || Math.random() < 0.5) {
			return null;
		}
		Node head = new Node((int) (Math.random() * maxValue));
		head.left = generate(level + 1, maxLevel, maxValue);
		head.right = generate(level + 1, maxLevel, maxValue);
		return head;
	}

	public static void main(String[] args) {
		int maxLevel = 10;
		int maxValue = 100;
		int testTimes = 1000000;
		for (int i = 0; i < testTimes; i++) {
			Node head = generateRandomBST(maxLevel, maxValue);
			if (maxWidthUseMap(head) != maxWidthNoMap(head)) {
				System.out.println("Oops!");
			}
		}
		System.out.println("finish!");

	}

}
